Distant barcodes [var. of Rearrange string k distance apart]

Time: O(KLogK); Space: O(K); medium

In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal.

You may return any answer, and it is guaranteed an answer exists.

Example 1:

Input: barcodes = [1,1,1,2,2,2]

Output: [2,1,2,1,2,1]

Example 2:

Input: barcodes = [1,1,1,1,2,2,3,3]

Output: [1,3,1,3,1,2,1,2]

Constraints:

  • 1 <= len(barcodes) <= 10000

  • 1 <= barcodes[i] <= 10000

Hints:

  1. We want to always choose the most common or second most common element to write next. What data structure allows us to query this effectively?

[7]:

import collections

class Solution1(object):
    """
    # Time: O(KlogK), K is the number of distinct barcodes
    # Space: O(K)
    """
    def rearrangeBarcodes(self, barcodes):
        """
        :type barcodes: List[int]
        :rtype: List[int]
        """
        cnts = collections.Counter(barcodes)
        sorted_cnts = [[v, k] for k, v in cnts.items()]
        sorted_cnts.sort(reverse=True)

        i = 0
        for v, k in sorted_cnts:
            for _ in range(v):
                barcodes[i] = k
                i += 2
                if i >= len(barcodes):
                    i = 1
        return barcodes

[8]:

s = Solution1()
barcodes = [1,1,1,2,2,2]
assert s.rearrangeBarcodes(barcodes) == [2,1,2,1,2,1]
barcodes = [1,1,1,1,2,2,3,3]
assert s.rearrangeBarcodes(barcodes) == [1,3,1,3,1,2,1,2]